package LeetCode;

public class LC_132_PalindromePartitioningII {
    public static void main(String[] args) {

    }

    static class Solution {

        public int minCut(String s) {
            int length = s.length();
            if (length <= 0) return 0;
            char[] chars = s.toCharArray();
            int[] nums = new int[length];
            boolean[][] isValid = new boolean[length][length];
            nums[0] = 0;
            for (int row = 0; row < length; row++) isValid[row][row] = true;
            for (int i = 1; i < chars.length; i++) {
                nums[i] = nums[i - 1] + 1;
                for (int j = 0; j < i; j++) {
                    if (chars[i] == chars[j]) {
                        if (i == j + 1 || isValid[j + 1][i - 1])
                            isValid[j][i] = true;
                    }
                    if (isValid[j][i]) {
                        if (j == 0)
                            nums[i] = 0;
                        else
                            nums[i] = Math.min(nums[i], nums[j - 1] + 1);
                    }
                }
            }
            return nums[chars.length - 1];
        }

    }
}
